use std::ptr;
const RB_TREE_NULL: *mut std::ffi::c_void = ptr::null_mut();
type RBTreeKey = *mut std::ffi::c_void;
type RBTreeValue = *mut std::ffi::c_void;
type RBTreeCompareFunc = fn(RBTreeValue, RBTreeValue) -> i32;
#[derive(Clone, Copy, PartialEq)]
enum RBTreeNodeColor {
    RB_TREE_NODE_RED,
    RB_TREE_NODE_BLACK,
}
#[repr(C)]
struct RBTreeNode {
    color: RBTreeNodeColor,
    key: RBTreeKey,
    value: RBTreeValue,
    parent: *mut RBTreeNode,
    children: [*mut RBTreeNode; 2],
}
#[repr(C)]
struct RBTree {
    root_node: *mut RBTreeNode,
    compare_func: RBTreeCompareFunc,
    num_nodes: i32,
}
#[derive(Clone, Copy)]
enum RBTreeNodeSide {}
fn rb_tree_node_side(node: *mut RBTreeNode) -> RBTreeNodeSide {
    unsafe {
        if (*(*node).parent).children[RB_TREE_NODE_LEFT] == node {
            RB_TREE_NODE_LEFT
        } else {
            RB_TREE_NODE_RIGHT
        }
    }
}
fn rb_tree_node_sibling(node: *mut RBTreeNode) -> *mut RBTreeNode {
    let side = rb_tree_node_side(node);
    unsafe { (*node).parent.children[1 - side as usize] }
}
fn rb_tree_node_uncle(node: *mut RBTreeNode) -> *mut RBTreeNode {
    rb_tree_node_sibling(unsafe { (*node).parent })
}
fn rb_tree_node_replace(tree: &mut RBTree, node1: &mut RBTreeNode, node2: Option<&mut RBTreeNode>) {
    if let Some(n) = node2 {
        n.parent = node1.parent;
    }
    if node1.parent.is_null() {
        tree.root_node = node2;
    } else {
        let side = rb_tree_node_side(node1);
        unsafe {
            (*node1.parent).children[side] = node2;
        }
    }
}
fn rb_tree_rotate<'a>(
    tree: &'a mut RBTree,
    node: &'a mut RBTreeNode,
    direction: RBTreeNodeSide,
) -> &'a mut RBTreeNode {
    let new_root: &'a mut RBTreeNode;
    new_root = node.children[(1 - direction as usize) as usize];
    rb_tree_node_replace(tree, node, new_root);
    node.children[(1 - direction as usize) as usize] = new_root.children[direction as usize];
    new_root.children[direction as usize] = node;
    node.parent = new_root;
    if node.children[(1 - direction as usize) as usize] != std::ptr::null_mut() {
        node.children[(1 - direction as usize) as usize].parent = node;
    }
    new_root
}
fn rb_tree_new(compare_func: RBTreeCompareFunc) -> *mut RBTree {
    let new_tree = unsafe { malloc(std::mem::size_of::<RBTree>()) as *mut RBTree };
    if new_tree.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*new_tree).root_node = ptr::null_mut();
        (*new_tree).num_nodes = 0;
        (*new_tree).compare_func = compare_func;
    }
    new_tree
}
fn rb_tree_free_subtree(node: *mut RBTreeNode) {
    if !node.is_null() {
        unsafe {
            rb_tree_free_subtree((*node).children[RB_TREE_NODE_LEFT]);
            rb_tree_free_subtree((*node).children[RB_TREE_NODE_RIGHT]);
            libc::free(node as *mut libc::c_void);
        }
    }
}
fn rb_tree_free(tree: *mut RBTree) {
    unsafe {
        rb_tree_free_subtree((*tree).root_node);
    }
    unsafe {
        libc::free(tree as *mut libc::c_void);
    }
}
fn rb_tree_insert_case1(tree: *mut RBTree, node: *mut RBTreeNode) {
    if unsafe { (*node).parent.is_null() } {
        unsafe {
            (*node).color = RB_TREE_NODE_BLACK;
        }
    } else {
        rb_tree_insert_case2(tree, node);
    }
}
fn rb_tree_insert_case2(tree: *mut RBTree, node: *mut RBTreeNode) {
    unsafe {
        if (*node).parent.as_ref().unwrap().color != RBTreeNodeColor::RB_TREE_NODE_BLACK {
            rb_tree_insert_case3(tree, node);
        }
    }
}
fn rb_tree_insert_case3(tree: *mut RBTree, node: *mut RBTreeNode) {
    let grandparent: *mut RBTreeNode;
    let uncle: *mut RBTreeNode;
    unsafe {
        grandparent = (*(*node).parent).parent;
        uncle = rb_tree_node_uncle(node);
        if !uncle.is_null() && (*uncle).color == RBTreeNodeColor::RED {
            (*(*node).parent).color = RBTreeNodeColor::BLACK;
            (*uncle).color = RBTreeNodeColor::BLACK;
            (*grandparent).color = RBTreeNodeColor::RED;
            rb_tree_insert_case1(tree, grandparent);
        } else {
            rb_tree_insert_case4(tree, node);
        }
    }
}
fn rb_tree_insert_case4(tree: &mut RBTree, node: &mut RBTreeNode) {
    let next_node: &mut RBTreeNode;
    let side;
    side = rb_tree_node_side(node);
    if side != rb_tree_node_side(node.parent) {
        next_node = node.parent;
        rb_tree_rotate(tree, node.parent, 1 - side);
    } else {
        next_node = node;
    }
    rb_tree_insert_case5(tree, next_node);
}
fn rb_tree_insert_case5(tree: &mut RBTree, node: &mut RBTreeNode) {
    let parent: &mut RBTreeNode;
    let grandparent: &mut RBTreeNode;
    let side: RBTreeNodeSide;
    parent = &mut *node.parent;
    grandparent = &mut *parent.parent;
    side = rb_tree_node_side(node);
    rb_tree_rotate(tree, grandparent, 1 - side as i32);
    parent.color = RB_TREE_NODE_BLACK;
    grandparent.color = RB_TREE_NODE_RED;
}
fn rb_tree_insert(tree: *mut RBTree, key: RBTreeKey, value: RBTreeValue) -> *mut RBTreeNode {
    use libc::malloc;
    use std::ptr;
    let node: *mut RBTreeNode;
    let mut rover: *mut *mut RBTreeNode;
    let mut parent: *mut RBTreeNode;
    let side: RBTreeNodeSide;
    unsafe {
        node = malloc(std::mem::size_of::<RBTreeNode>()) as *mut RBTreeNode;
        if node.is_null() {
            return ptr::null_mut();
        }
        (*node).key = key;
        (*node).value = value;
        (*node).color = RB_TREE_NODE_RED;
        (*node).children[RB_TREE_NODE_LEFT as usize] = ptr::null_mut();
        (*node).children[RB_TREE_NODE_RIGHT as usize] = ptr::null_mut();
        parent = ptr::null_mut();
        rover = &mut (*tree).root_node;
        while !(*rover).is_null() {
            parent = *rover;
            if ((*tree).compare_func)(value, (*(*rover)).value) < 0 {
                side = RB_TREE_NODE_LEFT;
            } else {
                side = RB_TREE_NODE_RIGHT;
            }
            rover = &mut (*(*rover)).children[side as usize];
        }
        *rover = node;
        (*node).parent = parent;
        rb_tree_insert_case1(tree, node);
        (*tree).num_nodes += 1;
        node
    }
}
fn rb_tree_lookup_node(tree: *mut RBTree, key: RBTreeKey) -> *mut RBTreeNode {
    let mut node = unsafe { (*tree).root_node };
    while !node.is_null() {
        let diff = unsafe { ((*tree).compare_func)(key, (*node).key) };
        if diff == 0 {
            return node;
        } else if diff < 0 {
            node = unsafe { (*node).children[RBTreeNodeSide::RB_TREE_NODE_LEFT as usize] };
        } else {
            node = unsafe { (*node).children[RBTreeNodeSide::RB_TREE_NODE_RIGHT as usize] };
        }
    }
    std::ptr::null_mut()
}
fn rb_tree_lookup(tree: *mut RBTree, key: RBTreeKey) -> RBTreeValue {
    let node = unsafe { rb_tree_lookup_node(tree, key) };
    if node.is_null() {
        std::ptr::null_mut()
    } else {
        unsafe { (*node).value }
    }
}
fn rb_tree_remove(tree: *mut RBTree, key: RBTreeKey) -> i32 {
    unsafe {
        let node = rb_tree_lookup_node(tree, key);
        if node.is_null() {
            return 0;
        }
        rb_tree_remove_node(tree, node);
        return 1;
    }
}
fn rb_tree_root_node(tree: *mut RBTree) -> *mut RBTreeNode {
    unsafe { (*tree).root_node }
}
fn rb_tree_node_key(node: *mut RBTreeNode) -> RBTreeKey {
    unsafe { (*node).key }
}
fn rb_tree_node_value(node: *mut RBTreeNode) -> RBTreeValue {
    unsafe { (*node).value }
}
fn rb_tree_node_child(node: *mut RBTreeNode, side: RBTreeNodeSide) -> *mut RBTreeNode {
    if side == RBTreeNodeSide::Left || side == RBTreeNodeSide::Right {
        unsafe { (*node).children[side as usize] }
    } else {
        std::ptr::null_mut()
    }
}
fn rb_tree_node_parent(node: *mut RBTreeNode) -> *mut RBTreeNode {
    unsafe { (*node).parent }
}
fn rb_tree_num_entries(tree: &RBTree) -> i32 {
    tree.num_nodes
}
